package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @description: leetcode 621. 任务调度器
 * @author 勾新杰
 * @version 1.0
 * @date 2025/2/14 11:20
 */
public class E621 {

    /**
     * <h3>方法一：贪心算法</h3>
     * @param tasks 任务列表
     * @param n 最大冷却时间
     * @return 最小时间
     */
    public int leastInterval1(char[] tasks, int n) {
        // 统计每个任务的出现次数
        int[] count = new int[26];
        for (char task : tasks) count[task - 'A']++;
        // 找到出现次数最多的任务
        int maxCount = 0;
        for (int num : count) maxCount = Math.max(maxCount, num);
        // 统计出现次数为 maxCount 的任务数量
        int countMax = 0;
        for (int num : count)
            if (num == maxCount)
                countMax++;
        // 计算最小时间
        int result = (maxCount - 1) * (n + 1) + countMax;
        return Math.max(result, tasks.length);
    }

    /**
     * <h3>方法二：优先队列</h3>
     * @param tasks 任务列表
     * @param n 最大冷却时间
     * @return 最小时间
     */
    public int leastInterval2(char[] tasks, int n) {
        // 统计每个任务的出现次数
        int[] count = new int[26];
        for (char task : tasks)
            count[task - 'A']++;
        // 将任务次数放入最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int num : count)
            if (num > 0) maxHeap.offer(num);
        int time = 0;
        while (!maxHeap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            // 每次取出 n + 1 个任务
            for (int i = 0; i <= n; i++) {
                if (!maxHeap.isEmpty()) {
                    int task = maxHeap.poll();
                    if (task > 1) temp.add(task - 1);
                }
                time++;
                if (maxHeap.isEmpty() && temp.isEmpty()) break;
            }
            // 将剩余任务重新放入堆中
            for (int task : temp) maxHeap.offer(task);
        }
        return time;
    }
}
